#!/usr/bin/python

from eulerlib import number

def generateDiagonalNums():
	cur=1;
	offset=2;
	side=1;
	count=0;
	
	yield (cur,offset+1);
	while True:
		cur+=offset;
		count+=1;
		if(count%4==0):
			offset+=2;
			side+=2;
		yield (cur,side);


def euler58():
	count=0;
	primecount=0;
	for (v,side) in generateDiagonalNums():
		if(v<2):
			continue;
		count+=1;
		if( number.is_prime(v) ):
			primecount+=1;
		if( primecount*10<count ):
			return side;
		#print "percent: %f, side: %d" % (float(primecount)/count, side);

print euler58();
